2382. Grafix Mask

In one mode of the grafix software package, the user blocks off portions of a masking layer using opaque rectangles. The bitmap used as the masking layer is 400 pixels tall and 600 pixels wide. Once the rectangles have been blocked off, the user can perform painting actions through the remaining areas of the masking layer, known as holes. To be precise, each hole is a maximal collection of contiguous pixels that are not covered by any of the opaque rectangles. Two pixels are contiguous if they share an edge, and contiguity is transitive.

You are given the rectangles that have been blocked off in the masking layer. Find the area, in pixels, of every hole in the resulting masking area, sorted from smallest area to greatest.

The left picture contains two holes, the right picture contains nine holes

Input. Consists of multiple test cases. The first line of each test case contains the number n (1 ≤ n ≤ 50) of given rectangles. Each of the next n lines gives the coordinates of opposite corners of rectangle in the form “row column row column” (0 ≤ row ≤ 399, 0 ≤ column ≤ 599). The first two integers are the coordinates of the top left pixel in the given rectangle, and the last two integers are the coordinates of its bottom right pixel.

Output. For each test case print in a separate line the list of hole areas in increasing order. If for some test case the resulting masking area does not contain holes, print an empty line.

Sample input

1

0 292 399 307

4

48 192 351 207

48 392 351 407

120 52 135 547

260 52 275 547

Sample output

116800 116800

22816 192608

SOLUTION

graphs – depth first search

Algorithm analysis

Будем трактовать точки полотна, покрытые хотя бы одним прямоугольником, водой, а точки, не покрытые ни одним прямоугольником, сушей. Тогда дырками будут являться острова. Задача сводится к нахождению количества островов и вычислению их размеров, что решается при помощи поиска в глубину.

При запуске процедуры поиска в глубину используется стек. Размеры слоя достаточно большие, поэтому потребуется большое количество памяти. В связи с архитектурой компьютерных программ, память, доступная для рекурсивных вызовов, мала. Поэтому следует брать память из кучи, что можно реализовать, например, используя структуру данных stack. Однако если стек промоделировать при помощи глобального массива, то скорость работы увеличится в разы.

Algorithm realization

Входной слой будем хранить в целочисленном массиве m. Объявим массив точек _Stack, в котором будем моделировать работу стека.

int m[400][600];

struct Point

{

int x, y;

Point(int _x = 0, int _y = 0) {x = _x; y = _y;}

} _Stack[1000000];

Нерекурсивная реализация поиска в глубину из точки (i, j). Функция dfs возвращает размер дырки, которой принадлежит точка (i, j).

int dfs(int i,int j)

{

int res = 0;

_Stack[ptr++] = Point(i,j);

Point node;

while(ptr > 0)

{

node = _Stack[--ptr];

if (m[node.x][node.y]) continue;

m[node.x][node.y] = 1;

res++;

if (node.x < 399) _Stack[ptr++] = Point(node.x+1,node.y);

if (node.x > 0) _Stack[ptr++] = Point(node.x-1,node.y);

if (node.y < 599) _Stack[ptr++] = Point(node.x,node.y+1);

if (node.y > 0) _Stack[ptr++] = Point(node.x,node.y-1);

}

return res;

}

Просматриваем слой слева направо и сверху вниз. Для каждой точки (j, k), не покрытой никаким прямоугольником (m[j][k] = 0), запускаем поиск в глубину dfs(j,k). Размеры дырок сохраняем в массиве res. По окончании работы функции sortedAreas сортируем массив дырок res и возвращаем его.

vector<int> sortedAreas(void)

{

vector<int> res;

int j, k;

for(ptr = j = 0; j < 400; j++)

for(k = 0; k < 600; k++)

{

if (m[j][k] == 1) continue;

res.push_back(dfs(j,k));

}

sort(res.begin(),res.end());

return res;

}

Основная часть программы. Считываем прямоугольники и наносим их на маскирующий слой. Таким образом, если точка (j, k) остается не покрытой никаким прямоугольником, то m[j][k] = 0. Иначе m[j][k] устанавливается равным 1.

while(scanf("%d",&n) == 1)

{

memset(m,0,sizeof(m));

for(i = 0; i < n; i++)

{

scanf("%d %d %d %d",&Top, &Left, &Down, &Right);

for(j = Top; j <= Down; j++)

for(k = Left; k <= Right; k++) m[j][k] = 1;

}

При помощи нерекурсивного поиска в глубину вычисляем размеры всех дырок и выводим их в возрастающем порядке.

res = sortedAreas();

for(i = 0; i < res.size(); i++) printf("%d ",res[i]);

printf("\n");

}